package 单调栈;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/11 16:22
 */
public class leetcode22括号生成 {



    /*
     这种递归的 方式, 主要体现的 是一种拆分的 思想:
     ** 生成 有效的括号 **
     把 **生成 括号**, 和 **括号的 有效性的判断** 分成两个 函数
     优点: 思路是比较清晰的
     缺点: 可不能 conding 不是最佳实践 (没法 进行剪枝操作)
     */
    public List<String> solution(int n){
        List<String> ans = new ArrayList<>();
        recursion(n,n,ans,new StringBuilder());
        return ans;
    }
    public void recursion(int left ,int right,List<String> ans,StringBuilder sb){
        if(left == 0 && right == 0){
            if(judge(sb.toString())){
                ans.add(sb.toString());
            }
            return ;
        }
        if(left < 0 || right < 0){
            return ;
        }
        // 选择  (
        sb.append('(');
        recursion(left - 1,right,ans,sb);
        // 回溯
        sb.deleteCharAt(sb.length() - 1);

        // 选择 )
        sb.append(')');
        recursion(left ,right - 1,ans,sb);
        sb.deleteCharAt(sb.length() - 1);
    }

    /*
     判断 括号的 合法性
     */
    public boolean judge(String s){
        char[] chars = s.toCharArray();
        int left = 0;
        for(char ch : chars){
            if(ch == '('){
                left++;
            }
            else{
                if(left > 0){
                    left--;
                }else{
                    return false;
                }
            }
        }
        return left == 0;
    }


    /*
     下面这个 递归:
     就是 ** 生成 括号, 和 有效性的判断是放在一块, 进行 计算的,
     可以进行剪枝  **
     */

    public void recursion(int left,int right,List<String> ans,String s,int n){
        if(left == n && right == n){
            ans.add(s);
            return ;
        }
        if(left > n){
            return ;
        }
        // 注意 这个 判断 条件, 很灵性, 保证了 left 始终 >= right
        if(left == 0 || left == right){
            recursion(left + 1,right,ans,s + "(",n);
        }
        else{ // left > right ,选择 ( or ) 都可以
            recursion(left + 1,right,ans,s + "(",n);
            recursion(left ,right + 1,ans,s + ")" ,n);
        }

    }
    /*
     确实 比原始字符串, 快了一点点!
     */
    public void recursion(int left,int right,List<String> ans,StringBuilder sb,int n){
        if(left == n && right == n){
            ans.add(sb.toString());
            return ;
        }
        if(left > n){
            return ;
        }
        // 注意 这个 判断 条件, 很灵性, 保证了 left 始终 >= right
        if(left == 0 || left == right){
            recursion(left + 1,right,ans,sb.append('('),n);
        }
        else{ // left > right ,选择 ( or ) 都可以
            recursion(left + 1,right,ans,sb.append('(') ,n);
            sb.deleteCharAt(sb.length() - 1);
            recursion(left ,right + 1,ans,sb.append(')') ,n);
        }
        sb.deleteCharAt(sb.length() - 1);

    }








    /*
      明白 我想测试的 是什么吧!
     */
    public void fa(){
        String s = "abc";
        StringBuilder sb = new StringBuilder(s);
        fb(sb.append("abc"));
        System.out.println(sb);
    }

    public void fb(StringBuilder s){
        System.out.println(s);
    }

    @Test
    public void test(){
        fa();
    }



}
